package LearnAlgorithm.d_标准查找算法and标准排序算法;

public class b6归并排序 {
	public static int[] helper;
	
	public static void main(String[] args) {
		int[] arr = new int[] {9,8,7,6,5,9,8,7,6,5,9,8,7,6,5};
		helper = new int[arr.length];
		long before = System.currentTimeMillis();
		mergeSort(arr, 0, arr.length - 1);
		util.Util.duration(before);
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
	}
	
	/**
	 * 归并排序
	 * O(NlogN)
	 * @param arr
	 * @param p
	 * @param r
	 */
	public static void mergeSort(int[] arr,int p, int r) {
		if (p < r) {//递归到最后，不通过这个判断，的时候，传入的数组里片段，只有两个元素了
			int mid = p + ((r - p) >>> 1);//找出此数组片段的中间索引
			mergeSort(arr, p, mid);//对左边排序
			mergeSort(arr, mid + 1, r);//对右边排序
			merge(arr,p,r,mid);//对排序好的两边进行合并
 		}
	}
	
	/**
	 * 归并核心
	 * @param arr
	 * @param p
	 * @param r
	 * @param mid
	 */
	public static void merge(int[] arr, int p, int r, int mid) {//mid是这个“数组片段”的“中间索引”
		copy(arr,helper,p,(r - p) + 1);//创建一个帮助空间，复制arr指定区域的元素
		/*
		 * 上面的参数(r - p) + 1指的是片段中的元素数
		 * 换言之就是要赋值几次
		 * 所以
		 * int temp = p;
			for (int i = 0; i < r; i++) {
				helper[temp] = arr[temp];
				temp++;
			}
		 * copy方法循环中的i=0而不是i=p。
		 * 艹这里的勾勾角角的烦人的细节真让人抓狂
		 */
		int left = p;//定义左侧的头部指针；指向待比较的元素
		int right = mid + 1;//定义右侧的头部指针；指向待比较的元素
		int current = p;//指向原数组待被填入数据的位置的指针
		while (left <= mid && right <= r) {
			/*
			 * 这个循环结束时：
			 * 情况1
			 * 左边(left)经过头(mid)了，右边(right)没到头(r),换句话说left这边所有值已存入，right还剩
			 * 那么left必定等于mid+1而且不再改变了；(因为mid存入了，就代表left==mid时if判断通过了，left会进行++)
			 * 此时右边剩下的数不动就行了；因为左右两边已经都是有序，现在的步骤是合并，右边只要剩下了数，就代表这些数大于前面所有的数
			 * 情况2
			 * 右边(right)经过r了，left没到mid，左边有剩
			 * 那么就需要新的循环将剩下的左边的数按顺序赋值到arr[current]
			 */
			if (helper[left] <= helper[right]) {
				arr[current] = helper[left];
				current++;
				left++;
			} else {
				arr[current] = helper[right];
				current++;
				right++;
			}
		}
		while (left <= mid) {//针对2情况，那么就需要新的循环将剩下的左边的数按顺序赋值到arr[current]
			arr[current] = helper[left];
			current++;
			left++;
		}
	}
	
	/**
	 * 复制	指定长度	指定起实元素	的	数组片段
	 * @param arr
	 * @param helper
	 * @param p
	 * @param r
	 */
	public static void copy(int[] arr, int[] helper, int p, int r) {
		for (int i = 0; i < r; i++) {//这里r代表传入的数组片段的长度！
			helper[p] = arr[p];//p是传入的数组片段的1开始的索引
			p++;
		}
	}
}


